
# 2 ~ 16
# 有  17 个元素的列表
# isNotPrime
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 列表每个元素的位置
# 1 1 0 0 1 0 1 0 1 1 1  0  1  0  1  1  1  列表每个元素的值 0-是素数 1-不是素数
# 当 2 是一个素数的时候
# 划掉 2 的 2 / 3 / 4 / 5 / 6 / 7 / 8 倍
# 当 3 是一个素数的时候
# 划掉 3 的 3 / 4 / 5 倍
# 当 5 是一个素数的时候
# 划掉 5 的 5 / 6 / 7 倍
# 7
# 7 / 8 / 9 / ... 倍
# 一些重复的情况
# 当 i 是一个素数的时候，从 i ^ 2 开始划掉合数。

#
# 假设 0-16 之间的所有数字都是素数
# 用算法筛掉这个范围里的合数
#

# n - 要查找素数的范围（最大值）
# eratosthenes(16) 0 - 16 之间的所有素数
def eratosthenes(n: int):
    # n + 1 个元素，每个元素都等于 0 的列表
    isNotPrime = [0] * (n + 1)

    # 初始情况
    isNotPrime[0] = 1 # 1 不是素数
    isNotPrime[1] = 1

    # 一般情况
    # 我们就要依赖 isNotPrime 这个列表，只要列表中为 0 的我们就认为是素数。
    # 只要 i * i <= n，我们就继续查找
    i = 0
    while i * i <= n:
        # 遇到素数，就标记它所有的倍数
        if isNotPrime[i] == 0:
            # i 是一个素数
            for j in range(i, (n // i) + 1):
                isNotPrime[i * j] = 1
        i += 1
    
    # 遍历 isNotPrime 列表，找到所有值为 0 的位置，这些位置代表的数字，都是素数。
    for i in range(0, len(isNotPrime)):
        if isNotPrime[i] == 0:
            print(i)

    return

eratosthenes(16)